package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class DeleteInBinarySearchTree450 {

    @Test
    public void test() {
        print(Arrays.asList(5,3,6,2,4,null,7), 3);
        print(Arrays.asList(2, 1), 2);
    }

    void print(List<Integer> list, int key) {
        TreeNode root = TreeNode.buildTree(list);
        //TreeNode root1 = deleteNode(root, key);
        TreeNode root1 = deleteNodeLooply(root, key);
        System.out.format("tree: %s\n", list);
    }

    public TreeNode deleteNode(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return deleteAndReturnNewRoot(root);
        }
        // 更新root节点的孩子, 有可能变了, 有可能没变
        if (val < root.val) {
            root.left = deleteNode(root.left, val);
        } else {
            root.right = deleteNode(root.right, val);
        }
        return root;
    }

    public TreeNode deleteAndReturnNewRoot(TreeNode root) {
        // 没有孩子 或 只有一个孩子 的情况
        if (root.left == null) {
            return root.right;
        } else if (root.right == null){
            return root.left;
        }

        // 有两个孩子的情况, 选取right的最小节点成为新root
        TreeNode minNodeParent = root;
        TreeNode minNode = root.right; // 这个还是需要, 因为初始时是往right, 循环内是往left
        while (minNode.left != null) {
            minNodeParent = minNode;
            minNode = minNode.left;
        }

        if (minNodeParent == root) {
            //循环一次都没进去过, minNode=root.right
            minNode.left = minNodeParent.left;
        } else {
            minNodeParent.left = minNode.right;
            minNode.left = root.left;
            minNode.right = root.right;
        }
        // destroy root if needed
        root.left = null;
        root.right = null;
        return minNode;
    }

    public TreeNode deleteNodeLooply(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        TreeNode parent = null;
        TreeNode target = root;
        while (target != null) {
            if (val == target.val) {
                break;
            } else if (val < target.val) {
                parent = target;
                target = target.left;
            } else {
                parent = target;
                target = target.right;
            }
        }

        if (target == null) {
            // not found
            return root;
        }

        // 只有一个孩子 或 没有孩子
        if (target.left == null || target.right == null) {
            TreeNode newTarget = (target.left != null) ? target.left : target.right;
            if (parent != null) {
                if (val < parent.val) {
                    parent.left = newTarget;
                } else {
                    parent.right = newTarget;
                }
                return root;
            } else {
                return newTarget;
            }
        }

        // 有两个孩子, 找到right的最大节点, 替换target
        TreeNode minNodeParent = target;
        TreeNode minNode = target.right; // 这个还是需要, 因为初始时是往right, 循环内是往left
        while (minNode.left != null) {
            minNodeParent = minNode;
            minNode = minNode.left;
        }

        if (minNodeParent == target) {
            //循环一次都没进去过: minNodeParent=target, minNode=target.right
            minNode.left = minNodeParent.left;
        } else {
            minNodeParent.left = minNode.right;
            minNode.left = target.left;
            minNode.right = target.right;
        }

        if (parent != null) {
            if (val < parent.val) {
                parent.left = minNode;
            } else {
                parent.right = minNode;
            }
            return root;
        } else {
            return minNode;
        }
    }
}
